/*
 * $Id: HashTable.h,v 1.7 2006-04-13 08:27:14 bacon Exp $
 */

#ifndef _XPP_BAS_HASHTABLE_CLASS_
#define _XPP_BAS_HASHTABLE_CLASS_

#include <xpp/Hashable.h>
#include <xpp/bas/Pair.h>
#include <xpp/bas/LinkedList.h>
#include <xp/bas/assert.h>

namespace xpp
{
	namespace bas
	{
		template <typename K, typename V>
		class HashTable
		{
		public:
			typedef Pair<K,V>   Entry;
			typedef LinkedList<Entry> Bucket;

			HashTable (xp_size_t bucket_size = 10, xp_size_t load_factor = 75)
			{
				this->entry_count = 0;
				this->bucket_size = bucket_size;
				this->buckets     = new Bucket[bucket_size];
				this->load_factor = load_factor;
				this->threshold   = bucket_size * load_factor / 100;
			}
			HashTable (const HashTable<K,V>& table)
			{
				this->entry_count = 0;
				this->bucket_size = table.bucket_size;
				this->buckets     = new Bucket[this->bucket_size];
				this->load_factor = table.load_factor;
				this->threshold   = this->bucket_size * this->load_factor / 100;

				for (xp_size_t i = 0; i < table.bucket_size; i++) {
					Bucket& b = table.buckets[i];
					typename Bucket::Node* np;
					for (np = b.head(); np != XP_NULL; np = np->forward()) {
						Entry& e = np->value;
						xp_size_t hc = e.key.hashCode() % this->bucket_size;
						this->buckets[hc].append (e);	
						this->entry_count++;
					}
				}

				// doesn't need to rehash in the copy constructor.
				//if (entry_count >= threshold) rehash ();
			}
			~HashTable ()
			{
				clear ();
				if (this->buckets != XP_NULL) delete[] this->buckets;
			}

			HashTable<K,V>& operator= (const HashTable<K,V>& table)
			{
				clear ();
				for (xp_size_t i = 0; i < table.bucket_size; i++) {
					Bucket& b = table.buckets[i];
					typename Bucket::Node* np;
					for (np = b.head(); np != XP_NULL; np = np->forward()) {
						Entry& e = np->value;
						xp_size_t hc = e.key.hashCode() % bucket_size;
						buckets[hc].append (e);	
						entry_count++;
					}
				}

				if (entry_count >= threshold) rehash ();
				return *this;
			}

			xp_size_t size () const
			{
				return this->entry_count;
			}

			bool isEmpty () const
			{
				return this->entry_count == 0;
			}

			xp_size_t bucketSize () const
			{
				return this->bucket_size;
			}

			Bucket& bucket (xp_size_t index) const
			{
				xp_assert (index < this->bucket_size);
				return this->buckets[index];	
			}			

			V& operator[] (const K& key)
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return e.value;
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				Entry& e2 = buckets[hc].append (Entry(key));
				entry_count++;
				return e2.value;
			}	

			const V& operator[] (const K& key) const
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return e.value;
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				Entry& e2 = buckets[hc].append (Entry(key));
				entry_count++;
				return e2.value;
			}	

			V* get (const K& key)
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return &e.value;
				}

				return XP_NULL;
			}

			const V* get (const K& key) const
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return &e.value;
				}

				return XP_NULL;
			}

			V* get (const K& key, 
				xp_size_t* hash_code, typename Bucket::Node** node)
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) {
						*hash_code = hc;
						*node = np;
						return &e.value;
					}
				}

				return XP_NULL;
			}

			const V* get (const K& key, 
				xp_size_t* hash_code, typename Bucket::Node** node) const
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) {
						*hash_code = hc;
						*node = np;
						return &e.value;
					}
				}

				return XP_NULL;
			}

			int put (const K& key, const V& value)
			{
				xp_size_t hc = key.hashCode() % bucket_size;

				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) {
						e.value = value;
						return 0;
					}
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				buckets[hc].append (Entry(key,value));
				entry_count++;
				return 0;
			}

			int putNew (const K& key, const V& value)
			{
				xp_size_t hc = key.hashCode() % bucket_size;

				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return -1;
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				buckets[hc].append (Entry(key,value));
				entry_count++;
				return 0;
			}

			V* insert (const K& key)
			{
				xp_size_t hc = key.hashCode() % bucket_size;

				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return &e.value;
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				Entry& e = buckets[hc].append (Entry(key));
				entry_count++;
				return &e.value;
			}

			V* insertNew (const K& key)
			{
				xp_size_t hc = key.hashCode() % bucket_size;

				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return XP_NULL;
				}

				if (entry_count >= threshold) {
					rehash ();
					hc = key.hashCode() % bucket_size;
				}

				Entry& e = buckets[hc].append (Entry(key));
				entry_count++;
				return &e.value;
			}

			int remove (const K& key) 
			{
				xp_size_t hc = key.hashCode() % this->bucket_size;

				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) {
						this->buckets[hc].remove (np);
						this->entry_count--;
						return 0;
					}
				}

				return -1;
			}

			int remove (xp_size_t hc, typename Bucket::Node* np)
			{
				//
				// WARNING: this method should be used with extra care.
				//
				this->buckets[hc].remove (np);
				this->entry_count--;
				return 0;
			}

			xp_size_t removeValue (const V& value)
			{
				xp_size_t count = 0;

				for (xp_size_t i = 0; i < this->bucket_size; i++) {
					typename Bucket::Node* np, * np2;
					np = buckets[i].head();
					while (np != XP_NULL) {
						Entry& e = np->value;
						np2 = np->forward ();
						if (value == e.value) {
							this->remove (i, np);
							count++;
						}
						np = np2;
					}
				}

				return count;
			}

			bool containsKey (const K& key) const
			{
				xp_size_t hc = key.hashCode() % bucket_size;
			
				typename Bucket::Node* np;
				for (np = buckets[hc].head(); np != XP_NULL; np = np->forward()) {
					Entry& e = np->value;
					if (key == e.key) return true;
				}

				return false;
			}

			bool containsValue (const K& value) const
			{
				for (xp_size_t i = 0; i < bucket_size; i++) {
					typename Bucket::Node* np;
					for (np = buckets[i].head(); 
					     np != XP_NULL; np = np->forward()) {
						Entry& e = np->value;
						if (value == e.value) return true;
					}
				}

				return false;
			}

			void clear ()
			{
				for (xp_size_t i = 0; i < bucket_size; i++) buckets[i].clear ();
				entry_count = 0;	
			}

			typedef int (HashTable<K,V>::*TraverseCallback) 
				(const Entry& entry, void* user_data) const;

			int traverse (TraverseCallback callback, void* user_data) const
			{
				for (xp_size_t i = 0; i < this->bucket_size; i++) 
				{
					typename Bucket::Node* np;
					for (np = buckets[i].head(); 
					     np != XP_NULL; np = np->forward()) 
					{
						const Entry& e = np->value;
						if ((this->*callback)(e,user_data) == -1) return -1;
					}
				}

				return 0;
			}
			
		protected:
			mutable xp_size_t  entry_count;
			mutable xp_size_t  bucket_size;
			mutable Bucket*    buckets;
			mutable xp_size_t  threshold;
			xp_size_t load_factor;

			void rehash () const
			{
				xp_size_t new_bucket_size = this->bucket_size * 2 + 1;
				Bucket* new_buckets = new Bucket[new_bucket_size];

				try {
					for (xp_size_t i = 0; i < this->bucket_size; i++) {
						typename Bucket::Node* np;
						for (np = buckets[i].head(); 
						     np != XP_NULL; np = np->forward()) {
							Entry& e = np->value;
							xp_size_t hc = e.key.hashCode() % new_bucket_size;
							new_buckets[hc].append (e);
						}
					}
				}
				catch (...) {
					delete[] new_buckets;
					throw;
				}

				delete[] this->buckets;
				this->buckets     = new_buckets;
				this->bucket_size = new_bucket_size;
				this->threshold   = 
					this->load_factor * this->bucket_size / 100;
			}
		};
	}
}

#endif
